//给你一个正整数 n。 
//
// 返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。 
//
// 置位 位指的是二进制表示中值为 1 的位。 
//
// 
//
// 示例 1： 
//
// 
// 输入： n = 5 
// 
//
// 输出： 7 
//
// 解释： 
//
// 7 的二进制表示是 "111"。 
//
// 示例 2： 
//
// 
// 输入： n = 10 
// 
//
// 输出： 15 
//
// 解释： 
//
// 15 的二进制表示是 "1111"。 
//
// 示例 3： 
//
// 
// 输入： n = 3 
// 
//
// 输出： 3 
//
// 解释： 
//
// 3 的二进制表示是 "11"。 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 1000 
// 
//
// Related Topics 位运算 数学 👍 18 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-10-29 15:15:02
 * @description 3370.仅含置位位的最小整数
 */
public class SmallestNumberWithAllSetBits{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SmallestNumberWithAllSetBits fun=new SmallestNumberWithAllSetBits();
	 	 Solution solution = fun.new Solution();
		  solution.smallestNumber(5);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //1. 位运算模拟
	// 2. 因为小于1000，直接二分
	public int smallestNumber(int n) {
		int[] ar = new int[]{1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863,134217727,268435455,536870911,1073741823};

		int l = 0, r = ar.length - 1;

		// 如果 n 大于等于数组最大值，返回 -1 或适当的值
		if (n >= ar[r]) {
			return -1; // 或者根据需求返回其他值
		}
		while (l < r) {
			int m = l + (r - l) / 2;
			if (ar[m] < n) {
				l = m + 1;
			} else {
				r = m;
			}
		}

		return ar[r];
	}
	public int smallestNumber1(int n) {
		int x = 1;
		while (x < n) {
			x = x * 2 + 1;
		}
		return x;
	}
	// 求出n的二进制长度，然后全部置为1则>=n
	public int smallestNumber2(int n) {
		// Integer.numberOfLeadingZeros(n) 返回 n 的二进制表示中前导零的数量
		int bitLength = 32 - Integer.numberOfLeadingZeros(n);
		return (1 << bitLength) - 1;
	}
	public int smallestNumber3(int n) {
		// 获取 n 的最高位的值（即最高的 1 所在的位置）
		return (Integer.highestOneBit(n) << 1) - 1;
	}



}
//leetcode submit region end(Prohibit modification and deletion)

}
